跳到主要内容

Deutsch-Jozsa 算法

nn 元 Hadamard 门的一个性质：

H⊗n∣j⟩=12n/2∑k=02n−1(−1)j⋅k∣k⟩H^{\otimes n}|j\rangle=\frac{1}{2^{n / 2}} \sum_{k=0}^{2^{n}-1}(-1)^{j \cdot k}|k\rangle

称一个 nn 元二值函数是常数的，如果它对所有的输入都给出同一个输出；称它是平衡的，如果它对所有的输入中给出 0 和 1 的数量相同。进一步假定这个函数的工作方式是把输出编码在一个量子位的相位中：

Of∣x⟩={∣x⟩ if f(x)=0−∣x⟩ if f(x)=1O_{f}|x\rangle=\left\{\begin{aligned}|x\rangle & \text { if } f(x)=0 \\-|x\rangle & \text { if } f(x)=1 \end{aligned}\right.

Deutsch-Jozsa 算法可以在一次运行中快速找出这个函数是常数的还是平衡的：

  1. 以 ∣0n⟩|0^n\rangle 开始
  2. 应用一个 nn 元 Hadamard 门
  3. 应用 OfO_f
  4. 再次应用一个 nn 元 Hadamard 门
  5. 观测，如果得到 ∣0n⟩|0^n\rangle 则是常数的，否则为平衡的。